package week07

// 28. 实现 strStr()
// https://leetcode-cn.com/problems/implement-strstr/

func strStr(haystack string, needle string) int {
	if needle == "" {
		return 0
	}
	var H = make([]int32, len(haystack)+1)
	for i := 1; i < len(H); i++ {
		H[i] = H[i-1] * b + int32(haystack[i-1] - 'a' + 1)
	}
	var needleH int32 = 0
	var p131 int32 = 1
	for i := range needle {
		needleH = needleH * b + int32(needle[i] - 'a' + 1)
		p131 = p131 * b
	}
	for i := len(needle); i <= len(haystack); i++ {
		if H[i] - H[i-len(needle)] * p131 == needleH {
			if haystack[i-len(needle):i] == needle {
				return i-len(needle)
			}
		}
	}
	return -1
}

const b int32 = 131
const p int64 = 1e9 + 7